Local area networks (LANs) are commonly used to transmit messages between relatively closely located computers. There are at least three basic types of organizational architectures for LANs: linear, ring and mesh. Ethernet, for example, is a widely used linear LAN for interconnecting computer workstations, mainframes, and minicomputers. The present invention concerns only mesh connected LANs.
Traditionally, while mesh connected LANs have been discussed in computer science literature and a few patents, mesh connected LANs have never achieved commercial success due to several well known and relatively intractable problems. One of those problems has been the lack of an efficient mechanism for routing messages through a mesh connected network. Ideally, the routing mechanism should be able to quickly route each packet received by a switch to a path that will bring the packet closer to its destination. The routing mechanism should also take advantage of the numerous pathways in a mesh connected network so that the network throughput exceeds the throughput of a single link.
Referring to FIG. 1, each switch S in the network 100 can receive data packets from several different input links, each of which must be routed to one or more output links. The switch must therefore have a mechanism for selecting a correct output link for each packet. To achieve high throughput, the network must use nonblocking switches which can simultaneously route many packets from various input links to different output links. In addition, it would preferable for the switch to allocate available output links to data packets fairly and yet quickly. A fair routing method is generally one which gives routing priority based on the order in which packets have been received.